import java.util.ArrayList;
import java.util.List;

/**
 * Description:
 * Date: 2025-11-11
 * Time: 16:43
 */
//孩子表示法模拟实现二叉树
public class BinaryTree {
    static class TreeNode{
        private char val;
        TreeNode left;
        TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    //先创建一棵树
    public TreeNode creatTree() {
        TreeNode nodeA = new TreeNode('A');
        TreeNode nodeB = new TreeNode('B');
        TreeNode nodeC = new TreeNode('C');
        TreeNode nodeD = new TreeNode('D');
        TreeNode nodeE = new TreeNode('E');
        TreeNode nodeF = new TreeNode('F');
        TreeNode nodeG = new TreeNode('G');

        nodeA.left = nodeB;
        nodeA.right = nodeC;
        nodeB.left = nodeD;
        nodeB.right = nodeE;
        nodeC.right = nodeG;
        nodeE.right = nodeF;

        return nodeA;
    }

    // 前序遍历
    void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
    // 中序遍历
    void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
    // 后序遍历
    void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    //返回二叉树节点值的前序遍历
    public List<Character> preorderTraversal(TreeNode root) {
        List<Character> list = new ArrayList<>();
        if (root == null) {
            return null;
        }
        list.add(root.val);
        List<Character> leftT = preorderTraversal(root.left);
        if (leftT != null) {
            list.addAll(leftT);
        }
        List<Character> rigthT = preorderTraversal(root.right);
        if (rigthT != null) {
            list.addAll(rigthT);
        }
        return list;
    }

    //返回二叉树节点值的中序遍历
    public List<Character> inorderTraversal(TreeNode root) {
        List<Character> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        List<Character> leftT = inorderTraversal(root.left);
        if (leftT != null) {
            list.addAll(leftT);
        }
        list.add(root.val);
        List<Character> rightT = inorderTraversal(root.right);
        if (rightT != null) {
            list.addAll(rightT);
        }
        return list;
    }

    //返回二叉树节点值的后序遍历
    public List<Character> postorderTraversal(TreeNode root) {
        List<Character> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        List<Character> leftT = postorderTraversal(root.left);
        if (leftT != null) {
            list.addAll(leftT);
        }
        List<Character> rightT = postorderTraversal(root.right);
        if (rightT != null) {
            list.addAll(rightT);
        }
        list.add(root.val);
        return list;
    }


}
